Integrated circuits (ICs) can be implemented to perform a variety of functions. Some ICs can be programmed to perform specified functions. One example of an IC that can be programmed is a field programmable gate array (FPGA). An FPGA typically includes an array of programmable tiles. These programmable tiles may include, for example, input/output blocks (IOBs), configurable logic blocks (CLBs), dedicated random access memory blocks (BRAM), multipliers, digital signal processing blocks (DSPs), processors, clock managers, delay lock loops (DLLs), and so forth.
Each programmable tile typically includes both programmable interconnect circuitry and programmable logic circuitry. The programmable interconnect circuitry typically includes a large number of interconnect lines of varying lengths interconnected or coupled by programmable interconnect points (PIPs). The programmable logic circuitry implements the logic of a user design using programmable elements that may include, for example, function generators, registers, arithmetic logic, and so forth.
The programmable interconnect and programmable logic circuitries are typically programmed by loading a stream of configuration data into internal configuration memory cells that define how the programmable elements are configured. The configuration data may be read from memory (e.g., from an external programmable read-only memory or PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
Another type of programmable IC is the complex programmable logic device, or CPLD. A CPLD includes two or more “function blocks” connected together and to input/output (I/O) resources by an interconnect switch matrix. Each function block of the CPLD includes a two-level AND/OR structure similar to those used in programmable logic arrays (PLAs) and programmable array logic (PAL) devices. In CPLDs, configuration data is typically stored on-chip in non-volatile memory. In some CPLDs, configuration data is stored on-chip in non-volatile memory, then downloaded to volatile memory as part of an initial configuration (programming) sequence.
For all of these programmable ICs, the functionality of the device is controlled by data bits provided to the device for that purpose. The data bits may be stored in volatile memory (e.g., static memory cells, as in FPGAs and some CPLDs), in non-volatile memory (e.g., FLASH memory, as in some CPLDs), or in any other type of memory cell.
Other programmable ICs are programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These programmable ICs are known as mask programmable devices. Programmable ICs may also be implemented in other ways, e.g., using fuse or antifuse technology. The phrase “programmable IC” may include, but is not limited to these devices and further may encompass devices that are only partially programmable. For example, one type of programmable IC includes a combination of hard-coded transistor logic and a programmable switch fabric that programmably interconnects the hard-coded transistor logic.
In order to implement a circuit design within an IC such as a programmable IC, the circuit design undergoes synthesis, mapping, placement, and routing. Synthesis generally refers to the process of converting an abstract, programmatic description of a circuit into a low-level design implementation. The abstract programmatic description of the circuit describes behavior of the circuit and, as such, is often referred to as a “behavioral description” of the circuit. The behavioral description of the circuit is also referred to as a register transfer level (RTL) description and is specified using a hardware description language (HDL). The low level design implementation generated through synthesis typically is specified as inter-connected logic gates.
Once synthesized, the resulting low-level circuit design is mapped, placed, and routed. Mapping is the process of correlating, or matching, the logic gates of the low-level circuit design to the types of actual circuit blocks or resources available in the particular IC in which the circuit design is to be implemented, i.e., the “target IC.” For example, one or more logic gates may be mapped to a single lookup table as the lookup table may implement a more complex logic function. The mapped circuit design specifies the same functionality as the low level circuit design, albeit in terms of the particular circuit blocks available on the target IC as opposed to lower-level logic gates.
Placement refers to the assignment of elements of the mapped circuit design to particular instances of the actual circuit blocks or resources on the target IC. Once placed, a circuit element of the circuit design has a specific location on the target IC corresponding to the instance of the circuit block and/or resource assigned thereto. Routing is the process of selecting particular routing resources such as wires, PIPs, and/or other interconnect circuitry to electrically couple the various circuit blocks of the target IC.
One technique used during place and/or route is delay budgeting. For each signal path (path) of the circuit design, a signal must be able to traverse the path within a finite and specified amount of time. The endpoints of a path are synchronous, or clocked, circuit elements. One or more combinatorial, e.g., un-clocked, circuit elements may be included within the path. Each segment of the path, referred to as a connection, has endpoints of: a synchronous circuit element and a combinatorial circuit element; a first combinatorial circuit element and a second combinatorial circuit element; or a combinatorial circuit element and a synchronous circuit element. Each connection may be allocated a portion of the maximum delay of the path referred to as a “delay budget.” The EDA tool operates upon connections of the path as opposed to the path as a whole.
Using delay budgets, the EDA tool performs placement and/or routing in a manner that seeks to optimize the circuit by avoiding delay budget violations. A delay budget violation is where the estimated delay of a connection exceeds the delay budget for the connection. With conventional EDA tools, the delay budgets are kept static during placement and routing operations. Treating delay budgets as static, however, results in out-of-date delay budgets that impose artificial constraints on the placement and/or routing processes, thereby limiting solution exploration. In consequence, sub-optimal placements and routings of the circuit design may result.